package likouJava;

import java.util.*;

public class 前K个高频元素 {

//    //小顶堆解法 O(n log k)
//    public int[] topKFrequent(int[] nums, int k) {
//        //1.统计每个数字出现的频率
//        Map<Integer, Integer> freqMap = new HashMap<>();
//        for (int num : nums){
//            freqMap.put(num, freqMap.getOrDefault(num,0) + 1);
//        }
//        //2.创建一个最小堆(按频率排序)
//        PriorityQueue<Map.Entry<Integer,Integer>>heap = new PriorityQueue<>((a,b) -> a.getValue() - b.getValue());
//
//        //3.遍历频率表，维护大小为k的堆
//        for (Map.Entry<Integer,Integer>entry : freqMap.entrySet()){
//            heap.offer(entry);
//            if (heap.size() > k){
//                heap.poll();  //移除频率最小的
//            }
//        }
//        //4.取出结果
//        int[] res = new int[k];
//        for (int i =  k - 1; i >= 0 ; i--) {
//            res[i] = heap.poll().getKey();
//        }
//        return res;
//    }

        //桶排序 O(n)
    public int[] topKFrequent(int[] nums, int k) {
        //1.统计频率
        Map<Integer,Integer>freqMap = new HashMap<>();
        for (int num : nums){
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        //2.建立桶,桶的下标代表出现的次数
        List<Integer>[] bucket = new List[nums.length + 1];
        for (int key : freqMap.keySet()){
            int freq = freqMap.get(key);
            if (bucket[freq] == null){
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(key);
        }

        //3.从高频往下找前k个
        List<Integer>resList = new ArrayList<>();
        for (int i = bucket.length - 1; i >= 0 ; i--) {
            if (bucket[i] != null){
                resList.addAll(bucket[i]);
            }
        }
        //4.转成数组返回
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = resList.get(i);
        }
        return res;
    }



}
